home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / drdobbs / 1991 / 02 / nelson / coder.c < prev    next >
C/C++ Source or Header  |  1990-06-03  |  6KB  |  206 lines
  1. /*
  2.  * Listing 2 -- coder.c
  3.  *
  4.  * This file contains the code needed to accomplish arithmetic
  5.  * coding of a symbol.  All the routines in this module need
  6.  * to know in order to accomplish coding is what the probabilities
  7.  * and scales of the symbol counts are.  This information is
  8.  * generally passed in a SYMBOL structure.
  9.  *
  10.  * This code was first published by Ian H. Witten, Radford M. Neal,
  11.  * and John G. Cleary in "Communications of the ACM" in June 1987,
  12.  * and has been modified slightly for this article.  The code
  13.  * is  published here with permission.
  14.  */
  15.  
  16. #include <stdio.h>
  17. #include "coder.h"
  18. #include "bitio.h"
  19.  
  20. /*
  21.  * These four variables define the current state of the arithmetic
  22.  * coder/decoder.  They are assumed to be 16 bits long.  Note that
  23.  * by declaring them as short ints, they will actually be 16 bits
  24.  * on most 80X86 and 680X0 machines, as well as VAXen.
  25.  */
  26. static unsigned short int code;  /* The present input code value       */
  27. static unsigned short int low;   /* Start of the current code range    */
  28. static unsigned short int high;  /* End of the current code range      */
  29. long underflow_bits;             /* Number of underflow bits pending   */
  30.  
  31. /*
  32.  * This routine must be called to initialize the encoding process.
  33.  * The high register is initialized to all 1s, and it is assumed that
  34.  * it has an infinite string of 1s to be shifted into the lower bit
  35.  * positions when needed.
  36.  */
  37. void initialize_arithmetic_encoder()
  38. {
  39.     low = 0;
  40.     high = 0xffff;
  41.     underflow_bits = 0;
  42. }
  43.  
  44. /*
  45.  * This routine is called to encode a symbol.  The symbol is passed
  46.  * in the SYMBOL structure as a low count, a high count, and a range,
  47.  * instead of the more conventional probability ranges.  The encoding
  48.  * process takes two steps.  First, the values of high and low are
  49.  * updated to take into account the range restriction created by the
  50.  * new symbol.  Then, as many bits as possible are shifted out to
  51.  * the output stream.  Finally, high and low are stable again and
  52.  * the routine returns.
  53.  */
  54. void encode_symbol( FILE *stream, SYMBOL *s )
  55. {
  56.     long range;
  57. /*
  58.  * These three lines rescale high and low for the new symbol.
  59.  */
  60.     range = (long) ( high-low ) + 1;
  61.     high = low + (unsigned short int )
  62.                  (( range * s->high_count ) / s->scale - 1 );
  63.     low = low + (unsigned short int )
  64.                  (( range * s->low_count ) / s->scale );
  65. /*
  66.  * This loop turns out new bits until high and low are far enough
  67.  * apart to have stabilized.
  68.  */
  69.     for ( ; ; )
  70.     {
  71. /*
  72.  * If this test passes, it means that the MSDigits match, and can
  73.  * be sent to the output stream.
  74.  */
  75.         if ( ( high & 0x8000 ) == ( low & 0x8000 ) )
  76.         {
  77.             output_bit( stream, high & 0x8000 );
  78.             while ( underflow_bits > 0 )
  79.             {
  80.                 output_bit( stream, ~high & 0x8000 );
  81.                 underflow_bits--;
  82.             }
  83.         }
  84. /*
  85.  * If this test passes, the numbers are in danger of underflow, because
  86.  * the MSDigits don't match, and the 2nd digits are just one apart.
  87.  */
  88.         else if ( ( low & 0x4000 ) && !( high & 0x4000 ))
  89.         {
  90.             underflow_bits += 1;
  91.             low &= 0x3fff;
  92.             high |= 0x4000;
  93.         }
  94.         else
  95.             return ;
  96.         low <<= 1;
  97.         high <<= 1;
  98.         high |= 1;
  99.     }
  100. }
  101.  
  102. /*
  103.  * At the end of the encoding process, there are still significant
  104.  * bits left in the high and low registers.  We output two bits,
  105.  * plus as many underflow bits as are necessary.
  106.  */
  107. void flush_arithmetic_encoder( FILE *stream )
  108. {
  109.     output_bit( stream, low & 0x4000 );
  110.     underflow_bits++;
  111.     while ( underflow_bits-- > 0 )
  112.         output_bit( stream, ~low & 0x4000 );
  113. }
  114.  
  115. /*
  116.  * When decoding, this routine is called to figure out which symbol
  117.  * is presently waiting to be decoded.  This routine expects to get
  118.  * the current model scale in the s->scale parameter, and it returns
  119.  * a count that corresponds to the present floating point code:
  120.  *
  121.  *  code = count / s->scale
  122.  */
  123. short int get_current_count( SYMBOL *s )
  124. {
  125.     long range;
  126.     short int count;
  127.  
  128.     range = (long) ( high - low ) + 1;
  129.     count = (short int)
  130.             ((((long) ( code - low ) + 1 ) * s->scale-1 ) / range );
  131.     return( count );
  132. }
  133.  
  134. /*
  135.  * This routine is called to initialize the state of the arithmetic
  136.  * decoder.  This involves initializing the high and low registers
  137.  * to their conventional starting values, plus reading the first
  138.  * 16 bits from the input stream into the code value.
  139.  */
  140. void initialize_arithmetic_decoder( FILE *stream )
  141. {
  142.     int i;
  143.  
  144.     code = 0;
  145.     for ( i = 0 ; i < 16 ; i++ )
  146.     {
  147.         code <<= 1;
  148.         code += input_bit( stream );
  149.     }
  150.     low = 0;
  151.     high = 0xffff;
  152. }
  153.  
  154. /*
  155.  * Just figuring out what the present symbol is doesn't remove
  156.  * it from the input bit stream.  After the character has been
  157.  * decoded, this routine has to be called to remove it from the
  158.  * input stream.
  159.  */
  160. void remove_symbol_from_stream( FILE *stream, SYMBOL *s )
  161. {
  162.     long range;
  163.  
  164. /*
  165.  * First, the range is expanded to account for the symbol removal.
  166.  */
  167.     range = (long)( high - low ) + 1;
  168.     high = low + (unsigned short int)
  169.                  (( range * s->high_count ) / s->scale - 1 );
  170.     low = low + (unsigned short int)
  171.                  (( range * s->low_count ) / s->scale );
  172. /*
  173.  * Next, any possible bits are shipped out.
  174.  */
  175.     for ( ; ; )
  176.     {
  177. /*
  178.  * If the MSDigits match, the bits will be shifted out.
  179.  */
  180.         if ( ( high & 0x8000 ) == ( low & 0x8000 ) )
  181.         {
  182.         }
  183. /*
  184.  * Else, if underflow is threatining, shift out the 2nd MSDigit.
  185.  */
  186.         else if ((low & 0x4000) == 0x4000  && (high & 0x4000) == 0 )
  187.         {
  188.             code ^= 0x4000;
  189.             low   &= 0x3fff;
  190.             high  |= 0x4000;
  191.         }
  192. /*
  193.  * Otherwise, nothing can be shifted out, so I return.
  194.  */
  195.         else
  196.             return;
  197.         low <<= 1;
  198.         high <<= 1;
  199.         high |= 1;
  200.         code <<= 1;
  201.         code += input_bit( stream );
  202.     }
  203. }
  204.  
  205.  
  206.